package code.oldCode.dynamic;

/**
 * @author cuihaoran
 * @date 2024/10/8
 */
public class StockProblem {

    /**
     * 121. 买卖股票的最佳时机
     *
     * @param prices
     * @return
     */
    public int maxProfit_121(int[] prices) {
        int max_profit = 0;
        int cost = Integer.MAX_VALUE;
        for (int price : prices) {
            cost = Math.min(cost, price);
            max_profit = Math.max(max_profit, price - cost);
        }
        return max_profit;
    }

    public int maxProfit_121_dp(int[] prices) {
        int len = prices.length;
        int[] buy = new int[len];
        int[] sell = new int[len];
        // 分为两种状态，截止到i，一次买、卖获得的最大利润
        // 这两种状态是有先后的
        buy[0] = -prices[0];
        sell[0] = 0;
        for (int i = 1; i < len; i++) {
            buy[i] = Math.max(buy[i - 1], -prices[i]);
            sell[i] = Math.max(sell[i - 1], buy[i] + prices[i]);
        }
        return sell[len - 1];
    }

    /**
     * 122. 买卖股票的最佳时机 II
     *
     * @param prices
     * @return
     */
    public int maxProfit_122(int[] prices) {
        int len = prices.length;
        // 分为两种状态，当前手里有股票的状态和当前没有股票的状态
        // 这两种状态是没先后的，因为这没规定买几次，可以买无限多次
        int[] dp_no_stock = new int[len];
        int[] dp_stock = new int[len];
        dp_stock[0] = -prices[0];
        dp_no_stock[0] = 0;
        for (int i = 1; i < len; i++) {
            dp_no_stock[i] = Math.max(dp_no_stock[i - 1], dp_stock[i - 1] + prices[i]);
            dp_stock[i] = Math.max(dp_stock[i - 1], dp_no_stock[i - 1] - prices[i]);
        }
        return dp_no_stock[len - 1];
    }

    /**
     * 123. 买卖股票的最佳时机 III
     *
     * @param prices
     * @return
     */
    public int maxProfit_123(int[] prices) {
        int len = prices.length;
        int[] buy1 = new int[len];
        int[] sell1 = new int[len];
        int[] buy2 = new int[len];
        int[] sell2 = new int[len];
        // 四种状态，第一次买、第一次卖、第二次买、第二次卖
        // 这四种状态是有先后的
        buy1[0] = -prices[0];
        sell1[0] = 0;
        buy2[0] = -prices[0];
        sell2[0] = 0;
        for (int i = 1; i < len; i++) {
            buy1[i] = Math.max(buy1[i - 1], -prices[i]);
            sell1[i] = Math.max(sell1[i - 1], buy1[i] + prices[i]);
            buy2[i] = Math.max(buy2[i - 1], sell1[i] - prices[i]);
            sell2[i] = Math.max(sell2[i - 1], buy2[i] + prices[i]);
        }
        return sell2[len - 1];
    }

    /**
     * 188. 买卖股票的最佳时机 IV
     *
     * @param prices
     * @return
     */
    public int maxProfit_188(int k, int[] prices) {
        // 123题的推广版
        int len = prices.length;
        int[][] buy = new int[k][len];
        int[][] sell = new int[k][len];
        for (int i = 0; i < k; i++) {
            buy[i][0] = -prices[0];
            sell[i][0] = 0;
        }
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < k; j++) {
                buy[j][i] = Math.max(buy[j][i - 1], (j == 0 ? 0 : sell[j - 1][i]) - prices[i]);
                sell[j][i] = Math.max(sell[j][i - 1], buy[j][i] + prices[i]);
            }
        }
        return sell[k - 1][len - 1];
    }

    /**
     * 309. 买卖股票的最佳时机含冷冻期
     *
     * @param prices
     * @return
     */
    public int maxProfit_309(int[] prices) {
        int len = prices.length;
        int[] no_stock = new int[len];
        int[] cool = new int[len];
        int[] stock = new int[len];
        no_stock[0] = 0;
        stock[0] = -prices[0];
        cool[0] = 0;
        for (int i = 1; i < len; i++) {
            no_stock[i] = Math.max(no_stock[i - 1], cool[i - 1]);
            stock[i] = Math.max(stock[i - 1], no_stock[i - 1] - prices[i]);
            cool[i] = stock[i] + prices[i];
        }
        return Math.max(no_stock[len - 1], cool[len - 1]);
    }

    /**
     * 714. 买卖股票的最佳时机含手续费
     *
     * @param prices
     * @param fee
     * @return
     */
    public int maxProfit_714(int[] prices, int fee) {
        int len = prices.length;
        int[] no_stock = new int[len];
        int[] stock = new int[len];
        no_stock[0] = 0;
        stock[0] = -prices[0];
        for (int i = 1; i < len; i++) {
            no_stock[i] = Math.max(no_stock[i - 1], stock[i - 1] + prices[i] - fee);
            stock[i] = Math.max(stock[i - 1], no_stock[i - 1] - prices[i]);
        }
        return no_stock[len - 1];
    }

    public static void main(String[] args) {
        StockProblem stockProblem = new StockProblem();
    }
}
